package com.code.test.ali;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.md
 * <p>
 * 40.组合总和II
 * 力扣题目链接
 * <p>
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
 * <p>
 * 示例 1:
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 * [1, 7],
 * [1, 2, 5],
 * [2, 6],
 * [1, 1, 6]
 * ]
 * 示例 2:
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 * [1,2,2],
 * [5]
 * ]
 */
public class TCode40 {


    public static void main(String[] args) {
        int[] nums = {10, 1, 2, 7, 6, 1, 5};
        List<List<Integer>> ret = combine(nums, 8);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    static List<List<Integer>> ret = new ArrayList<>();
    //每个组合
    static List<Integer> temp = new ArrayList<>();

    static boolean[] used;


    /**
     * 每个数字只能在组合中 使用一次：没有重复组合，数字只能在该组合中用一次，可以有重复数字
     */

    public static List<List<Integer>> combine(int[] nums, int target) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
//        Arrays.fill(used, false);
        bt(nums, target, 0);
        return ret;
    }

    /**
     * 同一个集合算子集，需要有index
     * 同一树枝可以重复，同一树层不能重复
     * [1,1,2]
     * 同一树层两个相同元素，不能重复使用
     * 因为第一个已经用过了，为什么第一个用过就不能再用，
     * eg：
     * 1 &[1,2] ->[1,1,2]、[1,2]
     * 如果此时:1 &[2] -> 就会出现 [1,2]跟上面一样相同元素
     */
    public static void bt(int[] nums, int target, int startIndex) {
        int sum = temp.stream()
                .mapToInt(Integer::intValue)
                .sum();
        if (sum == target) {
            ret.add(new ArrayList<>(temp));
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            int cur = nums[i];
            //终止条件
            if (sum + cur > target) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            temp.add(cur);
            used[i] = true;
            bt(nums, target, i + 1);
            used[i] = false;
            temp.remove(temp.size() - 1);
        }

    }


}
